package leetcode.newcoder;

import java.util.*;

/**
 * Created by tiang on 2018/8/3.
 * 题目描述
     小青蛙有一天不小心落入了一个地下迷宫,小青蛙希望用自己仅剩的体力值P跳出这个地下迷宫。
     为了让问题简单,假设这是一个n*m的格子迷宫,迷宫每个位置为0或者1,0代表这个位置有障碍物,
     小青蛙达到不了这个位置;1代表小青蛙可以达到的位置。小青蛙初始在(0,0)位置,
     地下迷宫的出口在(0,m-1)(保证这两个位置都是1,并且保证一定有起点到终点可达的路径),
     小青蛙在迷宫中水平移动一个单位距离需要消耗1点体力值,向上爬一个单位距离需要消耗3个单位的体力值,
     向下移动不消耗体力值,当小青蛙的体力值等于0的时候还没有到达出口,小青蛙将无法逃离迷宫。
     现在需要你帮助小青蛙计算出能否用仅剩的体力值跳出迷宫(即达到(0,m-1)位置)。
 输入描述:
     输入包括n+1行:
        第一行为三个整数n,m(3 <= m,n <= 10),P(1 <= P <= 100)
     接下来的n行:
        每行m个0或者1,以空格分隔
 输出描述:
    如果能逃离迷宫,则输出一行体力消耗最小的路径,输出格式见样例所示;如果不能逃离迷宫,则输出"Can not escape!"。 测试数据保证答案唯一
 */
public class 地下迷宫 {
    /**
     * 内部类
     */
    static class Node{
        private int x, y;
        private Node parent;
        private int left;

        public Node(int x,int y, int l, Node p){
            this.x = x;
            this.y = y;
            this.left = l;
            this.parent = p;
        }

        @Override
        public String toString() {
            return String.format("[%d,%d]", x, y);
        }

        @Override
        public int hashCode() {
            return x*10+y;
        }

        @Override
        public boolean equals(Object obj) {
            Node temp = (Node) obj;
            return x == temp.x && y == temp.y;
        }
    }

    /**
     * BFS，关键在于记录已经访问过的路径，采用一个hashset，重写节点的方法
     * @param map
     * @param hp
     */
    private static void findPath(int[][] map, int hp){
        List<Node> list = new ArrayList<>();
        list.add(new Node(0, 0, hp, null));
        Set<Node> set = new HashSet<>();
        while(!list.isEmpty()){
            List<Node> next = new ArrayList<>();
            for(Node pos: list){
                if(pos.y+1<map[0].length && map[pos.x][pos.y+1] == 1 && pos.left >= 1){
                    next.add(new Node(pos.x, pos.y+1, pos.left-1, pos));
                }
                if(pos.y-1>=0 && map[pos.x][pos.y-1] == 1 && pos.left >= 1)
                    next.add(new Node(pos.x, pos.y-1, pos.left-1, pos));
                if(pos.x+1<map.length && map[pos.x+1][pos.y] == 1)
                    next.add(new Node(pos.x+1, pos.y, pos.left, pos));
                if(pos.x-1>=0 && map[pos.x-1][pos.y] == 1 && pos.left>=3)
                    next.add(new Node(pos.x-1, pos.y, pos.left-3, pos));
            }
            List<Node> tl = new ArrayList<>();
            for(Node node : next){
                if(set.contains(node))
                    continue;
                else{
                    tl.add(node);
                    set.add(node);
                    if(node.x == 0 && node.y == map[0].length-1){
                        Node temp = node;
                        Stack<Node> stack = new Stack<>();
                        while(temp!=null){
                            stack.push(temp);
                            temp = temp.parent;
                        }
                        StringBuilder sb = new StringBuilder();
                        while(!stack.isEmpty()){
                            sb.append(stack.pop()).append(',');
                        }
                        sb.deleteCharAt(sb.length()-1);
                        System.out.println(sb);
                        return;
                    }
                }
            }
            list = tl;
        }
        System.out.println("Can not escape!");
    }

    /**
     * 上面是BFS,下面是DFS
     */

    /**
     * DFS，关键在于一条路径中要尽可能的避免无用的环形，所以采用一个visited数组，标记在一条路径中访问过的元素
     * 这条路径结束之后再置为false
     * @param map
     * @param hp
     */
    private static void findPahtDFS(int[][] map, int hp){
        String result = isRightPath(0, 0, hp, map, new boolean[map.length][map[0].length]);
        if(result==null)
            System.out.println("Can not escape!");
        else
            System.out.println(result);
    }

    private static String isRightPath(int x, int y, int hp, int[][] map, boolean[][] visited){
        if(!(x>=0&&x<map.length && y>=0 && y<map[0].length && hp>=0 && map[x][y] == 1))
            return null;
        if(visited[x][y])
            return null;
        if(x == 0 && y == map[0].length-1){
            return String.format("[%d,%d]", x,y);
        }
        visited[x][y] = true;
        String down = isRightPath(x+1, y, hp, map, visited),
                right = isRightPath(x, y+1, hp-1, map, visited),
                up = isRightPath(x-1, y, hp-3, map, visited),
                left = isRightPath(x, y-1, hp-1, map, visited);
        String result = null;
        result = getResult(down, getResult(up, getResult(left, getResult(right, result))));
        if(result!=null)
            result = String.format("[%d,%d]",x,y)+","+result;
        visited[x][y] = false;
        return result;
    }

    private static String getResult(String value, String result) {
        if (value == null)
            return result;
        return result == null ? value : result.length() > value.length() ? value : result;
    }
}
